# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        def func(node, res):
            if node is None:
                return 0
            left_val = func(node.left, res)
            right_val = func(node.right, res)
            node_val = node.val
            node_val = max(node_val, node_val + left_val)
            node_val = max(node_val, node_val + right_val)

            res[0] = max(node_val, res[0])

            return max(node.val, node.val + left_val, node.val + right_val)

        res = [-2**31]
        func(root, res)

        return res[0]
